#include<iostream>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<set>
#include<time.h>
using namespace std;
int main()
{
	srand(time(0));
	int N = 1000000;

	vector<int> v;
	for (int i = 0; i < N; i++)
	{
		v.push_back(rand());//无序且重复多的的数字插入时hash的效率更高,hash查找的效率更高
		//v.push_back(i);
		//v.push_back(rand()+i);
	}
	//哈希底层也是树，但是不是有序树
	set<int> s;
	int begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	int end1 = clock();
	cout << "set take time " << end1 - begin1 << endl;

	//
	unordered_set<int> us;
	int begin2 = clock();
	for (auto e : v)
	{
		us.insert(e);
	}
	int end2 = clock();
	cout << "unordered_set take time " << end2 - begin2 << endl;

	cout << s.size() << endl;
	cout << us.size() << endl;

	//比较find的效率
	int begin3 = clock();
	for (auto e : v)
	{
		s.find(e);
	}
	int end3 = clock();
	cout << "set find take time " << end3 - begin3 << endl;

	int begin4 = clock();
	for (auto e : v)
	{
		us.find(e);
	}
	int end4 = clock();
	cout << "unordered_set find take time " << end4 - begin4 << endl;

	//比较erase的效率
	int begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	int end5 = clock();
	cout << "set erase take time " << end5 - begin5 << endl;

	int begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	int end6 = clock();
	cout << "unordered_set erase take time " << end6 - begin6 << endl;
	cout << s.size() << endl;
	cout << us.size() << endl;
	return 0;
}